package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-27
 */

/**
 * 给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针
 * 例如，
 * 给出的链表为: 1→2→3→4→5, n=2.
 * 删除了链表的倒数第 n 个节点之后,链表变为 1→2→3→5.
 *
 * 备注：
 * 题目保证 n 一定是有效的
 * 请给出请给出时间复杂度为 O(n) 的算法
 */
public class NC53 {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode dum = new ListNode();
        dum.next = head;
        ListNode h = head;
        for (int i = 1; i < n; i++) h = h.next;
        ListNode pre = dum;
        while (h.next!=null){
            pre = head;
            head = head.next;
            h = h.next;
        }
        pre.next = head.next;
        return dum.next;
    }
}
